package cn.aylog.arrayQueue;

import java.util.Scanner;

/**
 * 数据结构与算法 之
 *  队列: 先进先出
 */
public class Main {
    public static void main(String[] args) {
        CircleArrayQueue queue = new CircleArrayQueue(3);
        Scanner sc = new Scanner(System.in);
        boolean loop = true;
        while(loop) {
            System.out.println("a(add)");
            System.out.println("g(get)");
            System.out.println("h(head)");
            System.out.println("l(list)");
            System.out.println("e(exit)");
            System.out.println("请选择:");
            char key = sc.next().charAt(0);
            try {
                switch (key) {
                    case 'a':
                        System.out.println("请输入一个数:");
                        int val = sc.nextInt();
                            queue.add(val);
                        break;
                    case 'g':
                        int res = queue.get();
                        System.out.printf("已取出值为: %d\n", res);
                        break;
                    case 'h':
                        int ret = queue.head();
                        System.out.printf("队头数据为: %d\n", ret);
                        break;
                    case 'l':
                        queue.list();
                        break;
                    case 'e':
                        loop = false;
                        sc.close();
                        break;
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        System.out.println("退出...");
    }
}

/**
 * 使用数组模拟队列
 */
class ArrayQueue {
    private int data[];
    private int maxSize = 8;
    private int front = -1; // 指向当前队列的第一个元素的前一个节点
    private int rare = -1; // 指向当前队列的最后一个

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new int[this.maxSize];
    }

    /**
     * 添加元素
     */
    public void add(int n) {
        if(isFull()) {
            System.out.println("队列已满~");
            return;
        }
        getNextRare();
        data[rare] = n;
    }

    /**
     * 获取队头元素, 同时移除
     */
    public int get() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空~");
        }
        getNextFront();
        int res = data[front];
        data[front] = 0;
        return res;
    }

    /**
     * 查看队头元素, 不移除
     */
    public int head() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空~");
        }
        return data[front + 1];
    }

    /**
     * 显示所有元素
     */
    public void list() {
        if(isEmpty()) {
            System.out.println("队列为空~");
            return;
        }
        for(int i=0; i<data.length; i++) {
            System.out.printf("data[%d]=%d \n", i, data[i]);
        }
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return rare == front;
    }

    /**
     * 判断队列是否已满
     */
    public boolean isFull() {
        return Math.abs(rare - front) == maxSize;
    }

    /**
     * 获取头指针
     */
    private int getNextFront() {
        front++;
        return front;
    }

    /**
     * 获取尾指针
     */
    private int getNextRare() {
        rare++;
        return rare;
    }
}

/**
 * 使用数组模拟环形队列
 */
class CircleArrayQueue {
    private int data[];
    private int maxSize;
    private int front; // 指向第一个元素
    private int rear; // 指向下一个可插入的节点
    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize + 1;
        data = new int[this.maxSize];

    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 判断队列是否已满
     */
    public boolean isFull() {
         return (rear + 1) % maxSize == front;
    }

    /**
     * 有效数据个数
     */
    public int getSize() {
         return (rear + maxSize - front) % maxSize;
    }
    /**
     * 添加元素
     */
    public void add(int n) {
        if(isFull()) {
            System.out.println("队列已满~");
            return;
        }
        int idx = rear % maxSize;
        this.data[idx] = n;
        rear++;
    }

    /**
     * 获取队头元素, 同时移除
     */
    public int get() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空~");
        }
        int idx = front % maxSize;
        int res = data[idx];
        data[idx] = 0;
        front++;
        return res;
    }

    /**
     * 查看队头元素, 不移除
     */
    public int head() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空~");
        }
        return data[front % maxSize];
    }

    /**
     * 显示所有元素
     */
    public void list() {
        if(isEmpty()) {
            System.out.println("队列为空~");
            return;
        }
        int start = front % maxSize;
        int end = start + getSize();
        for(int i=start; i<end; i++) {
            System.out.printf("data[%d]=%d \n", i, data[i]);
        }
    }
}
